package org.ala.linshen.dp;

/**
 * 给你一个大小为 m x n 的矩阵 grid 。最初，你位于左上角 (0, 0) ，每一步，你可以在矩阵中 向右 或 向下 移动。
 *
 * 在从左上角 (0, 0) 开始到右下角 (m - 1, n - 1) 结束的所有路径中，找出具有 最大非负积 的路径。路径的积是沿路径访问的单元格中所有整数的乘积。
 *
 * 返回 最大非负积 对 109 + 7 取余 的结果。如果最大积为 负数 ，则返回 -1 。
 *
 * 注意，取余是在得到最大积之后执行的。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：grid = [[-1,-2,-3],[-2,-3,-3],[-3,-3,-2]]
 * 输出：-1
 * 解释：从 (0, 0) 到 (2, 2) 的路径中无法得到非负积，所以返回 -1 。
 * 示例 2：
 *
 *
 * 输入：grid = [[1,-2,1],[1,-2,1],[3,-4,1]]
 * 输出：8
 * 解释：最大非负积对应的路径如图所示 (1 * 1 * -2 * -4 * 1 = 8)
 * 示例 3：
 *
 *
 * 输入：grid = [[1,3],[0,-4]]
 * 输出：0
 * 解释：最大非负积对应的路径如图所示 (1 * 0 * -4 = 0)
 *
 *
 * 提示：
 *
 * m == grid.length
 * n == grid[i].length
 * 1 <= m, n <= 15
 * -4 <= grid[i][j] <= 4
 *
 * @author ala
 * @date 2024-09-19 12:17
 */
public class Q1594 {

    public static void main(String[] args) {
        Q1594 q = new Q1594();

//        int[][] grid = {
//                {-1,-2,-3},
//                {-2,-3,-3},
//                {-3,-3,-2}};
        int[][] grid = {{1,-2,1},{1,-2,1},{3,-4,1}};

        System.out.println(q.maxProductPath(grid));
    }

    public int maxProductPath(int[][] grid) {
        return V1(grid);
    }
    static int MOD = (int)1e9 + 7,
               INF = (int)-1e4;
    /**
     *  1）dp[i][j][0 | 1]表示(i-1,j-1)位的路径积的最大最小
     *  2）如果 grid[i - 1][j - 1] > 0
     *          dp[i][j][0] = max(dp[i - 1][j][0], dp[i][j - 1][0]) * grid[i - 1][j - 1]
     *          dp[i][j][1] = max(dp[i - 1][j][1], dp[i][j - 1][1]) * grid[i - 1][j - 1]
     *      如果 grid[i - 1][j - 1] < 0
     *          dp[i][j][0] = max(dp[i - 1][j][1], dp[i][j - 1][1]) * grid[i - 1][j - 1]
     *          dp[i][j][1] = min(dp[i - 1][j][0], dp[i][j - 1][0]) * grid[i - 1][j - 1]
     *      如果 如果 grid[i - 1][j - 1] == 0
     *          dp[i][j][0] = dp[i][j][1] = 0
     *  3）dp[0][j] = dp[i][0] = 1
     *  4）最后dp[M][N]就是答案
     */
    protected int V1(int[][] grid) {
        int M = grid.length, N = grid[0].length;

        long[][] dp1 = new long[M][N],
                 dp2 = new long[M][N];
        dp1[0][0] = dp2[0][0] = grid[0][0];
        for (int i = 1 ; i < M ; i++) { dp1[i][0] = dp2[i][0] = dp1[i - 1][0] * grid[i][0]; }
        for (int j = 1 ; j < N ; j++) { dp1[0][j] = dp2[0][j] = dp1[0][j - 1] * grid[0][j]; }

        for (int i = 1 ; i < M ; i++) {
            for (int j = 1 ; j < N ; j++) {
                long v = grid[i][j];
                if (v > 0) {
                    dp1[i][j] = Math.max(dp1[i - 1][j], dp1[i][j - 1]) * v;
                    dp2[i][j] = Math.min(dp2[i - 1][j], dp2[i][j - 1]) * v;
                } else if (v < 0) {
                    dp1[i][j] = Math.min(dp2[i - 1][j], dp2[i][j - 1]) * v;
                    dp2[i][j] = Math.max(dp1[i - 1][j], dp1[i][j - 1]) * v;
                } else {
                    dp1[i][j] = dp2[i][j] = 0;
                }

            }
        }

        return dp1[M - 1][N - 1] < 0 ? -1 : (int)(dp1[M - 1][N - 1] % MOD);
    }
}
